#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define Status int
#define ElemType int


// 链表节点结构体
typedef struct QNode {
    ElemType data;          // 节点数据
    struct QNode *next;     // 指向下一个节点的指针
} QNode, *QueuePtr;

// 链式队列结构体（包含队头和队尾指针）
typedef struct {
    QueuePtr front;  // 队头指针（指向头节点，头节点不存数据）
    QueuePtr rear;   // 队尾指针（指向最后一个元素节点）
} LinkQueue;

//初始化 头指向的地址就是队列首地址，代表整个队列（数组那种感觉）
Status InitQueue(LinkQueue *Q){
    Q->front = (QNode*)malloc(sizeof(QNode));
    Q->rear = Q->front;
    if(!Q->front)return ERROR;
    Q->rear->next=NULL;//队尾指向
    return OK;
}
//销毁
// 销毁队列
Status DestroyQueue(LinkQueue *Q) {
    while (Q->front) {  // 循环释放所有节点，直到 front 为空
        Q->rear = Q->front->next;  // 步骤1：用 rear 临时保存当前头节点的下一个节点
        free(Q->front);    // 步骤2：释放当前头节点（第一次是头节点，后续是元素节点）
        Q->front = Q->rear;        // 步骤3：将 front 移动到下一个节点（继续释放）
    }
    return OK;
}
// 判断队列是否为空（头节点的 next 为空则空）
Status IsEmpty(LinkQueue *Q) {
    return (Q->front->next == NULL) ? OK : ERROR;
}
//入队
Status EnQueue(LinkQueue *Q,ElemType e){
    QueuePtr p = (QueuePtr)malloc(sizeof(QNode));  // 创建新节点（新来的人）
    p->data = e;  // 存元素值
    p->next = NULL;  // 新节点后面暂时没人
    Q->rear->next = p;  // 原来的队尾节点后面接上新节点
    Q->rear = p;  // 队尾指针移到新节点（现在它是最后一个）
    return OK;
}
//出队
Status DeQueue(LinkQueue *Q,ElemType *e){
    //空？
    if(IsEmpty(Q)){
        return ERROR;
    }
    //局部节点
    QueuePtr p =Q->front ->next;
    *e=p->data;
    Q->front->next=p->next;
    if(p==Q->rear)
    Q->rear=Q->front;
    free(p);
    
    return OK;
}
//队头元素查看
Status GetFront(LinkQueue *Q,ElemType* e){
    if(Q->rear==Q->front){
        return ERROR;
    }
    *e=Q->front->next->data;
    return OK;
}

// 打印队列
void PrintQueue(LinkQueue *Q) {
    if (IsEmpty(Q)) {
        printf("队列为空\n");
        return;
    }
    printf("队列元素：");
    QueuePtr p = Q->front->next;
    while (p) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

//
int main(){
    LinkQueue Q;
    InitQueue(&Q);
    EnQueue(&Q, 1);
    EnQueue(&Q, 2);
    EnQueue(&Q, 3);
    PrintQueue(&Q);  // 1 2 3

    int e;
    DeQueue(&Q, &e);  // 出队1
    PrintQueue(&Q);  // 2 3

    EnQueue(&Q, 4);  // 动态扩容，无容量限制
    PrintQueue(&Q);  // 2 3 4
    return 0;
}